﻿#include "Index.h"

class IZigZagConvert
{
public:
	/**
	 * Z字形变换.
	 * https://leetcode.cn/problems/zigzag-conversion/
	 *
	 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
	 *
	 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
	 * P   A   H   N
	 * A P L S I I G
	 * Y   I   R
	 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
	 */
	virtual std::string convert(std::string s, int numRows) = 0;
};


class ZigZagConvert
{
public:
	class Monitor:public IZigZagConvert
	{
	public:
		/**
		 * 行模拟法.
		 * 每个Z字行对应一个新建字符串，遍历输入的字符串，遍历到的字符依次存储进对应的Z字行中。
		 * 遍历字符串结束后，按照从上到下的顺序合并每个Z字行的字符串到转换后的结果串中。
		 *
		 * 时间:O(n) 空间:O(0)
		 */
		std::string convert(std::string s, int numRows) override
		{
			if (numRows <= 1)
				return s;

			std::vector<std::string> zigzagRows(numRows, "");
			int rowIndex = 0;
			int dir = 1;

			const int strSize = s.size();
			for (int i = 0; i < strSize; ++i)
			{
				zigzagRows[rowIndex] += s[i];

				const int nextRowIndex = rowIndex + dir;
				if (nextRowIndex >= numRows || nextRowIndex < 0)
					dir = -dir;

				rowIndex += dir;
			}

			std::string result;
			for (const auto& rowStr : zigzagRows)
				result += rowStr;
			return result;
		}
	};

	class DirectTransfer:public IZigZagConvert
	{
	public:
		/**
		 * 直接转换法.
		 * 时间:O(n) 空间:O(1)
		 */
		std::string convert(std::string s, int numRows) override
		{
			if (numRows == 1)
				return s;

			std::string result;
			const int cycle_cnt = 2 * numRows - 2;
			const int s_size = s.size();

			for (int i = 0; i < numRows; ++i)
			{
				if (i == 0 || i == numRows - 1)
				{
					int k = i == 0 ? 0 : numRows - 1;
					while (k < s_size)
					{
						result += s.at(k);
						k += cycle_cnt;
					}
				}
				else
				{
					int k0 = i;
					int k1 = cycle_cnt - k0;
					while (k0 < s_size)
					{
						result += s.at(k0);
						if (k1 < s_size)
							result += s.at(k1);

						k0 += cycle_cnt;
						k1 += cycle_cnt;
					}
				}
			}
			return result;
		}
	};
};
